0754. 到达终点数字【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学

1. 📝 题目描述

• leetcode

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

• 每次你可以选择向左或向右移动。
• 第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target，返回到达目标所需的 最小 移动次数(即最小 numMoves)。

---

示例 1：

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1。
第二次移动，从 1 到 -1。
第三次移动，从 -1 到 2。

示例 2：

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1。
第二次移动，从 1 到 3。

---

提示：

• -10^9 <= target <= 10^9
• target != 0

2. 🎯 s.1 - 数学

c

int reachNumber(int target) {
    if (target < 0) target = -target;
    int sum = 0, step = 0;
    while (sum < target || (sum - target) % 2 != 0) {
        step++;
        sum += step;
    }
    return step;
}

js

/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function (target) {
  target = Math.abs(target)
  let sum = 0,
    step = 0
  while (sum < target || (sum - target) % 2 !== 0) {
    step++
    sum += step
  }
  return step
}

py

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s, step = 0, 0
        while s < target or (s - target) % 2 != 0:
            step += 1
            s += step
        return step

• 时间复杂度：$O(\sqrt{|target|})$
• 空间复杂度：$O(1)$

算法思路：

• 由对称性可取 target 的绝对值
• 累加 1+2+...+step 直到 sum ≥ target 且 (sum - target) 为偶数
• 因为将某一步从 +k 变为 -k，sum 减少 2k，差值必须是偶数才能等量抵消